//给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重
//复的三元组。
//
// 注意：答案中不可以包含重复的三元组。
//
//
//
// 示例 1：
//
//
//输入：nums = [-1,0,1,2,-1,-4]
//输出：[[-1,-1,2],[-1,0,1]]
//
//
// 示例 2：
//
//
//输入：nums = []
//输出：[]
//
//
// 示例 3：
//
//
//输入：nums = [0]
//输出：[]
//
//
//
//
// 提示：
//
//
// 0 <= nums.length <= 3000
// -10⁵ <= nums[i] <= 10⁵
//
// Related Topics 数组 双指针 排序 👍 4905 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class 三数之和 {
    public static void main(String[] args) {
        Solution solution = new 三数之和().new Solution();
        System.out.println(solution.threeSum(new int[]{-5, -4, -3, -2, -1, -1, 0, 1, 2, 3, 4, 5}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> ans = new ArrayList<>();
            for (int i = nums.length - 1; i > 1; i--) {
                if (i == nums.length - 1 || nums[i] != nums[i + 1]) {
                    List<List<Integer>> nexts = twoSum(nums, i - 1, -nums[i]);
                    for (List<Integer> cur : nexts) {
                        cur.add(nums[i]);
                        ans.add(cur);
                    }
                }
            }
            return ans;
        }

        //两数之和 从0开始到end位置
        public List<List<Integer>> twoSum(int[] nums, int end, int target) {
            //双指针
            int L = 0, R = end;
            List<List<Integer>> ans = new ArrayList<>();
            while (L < R) {
                if (nums[L] + nums[R] > target) {
                    R--;
                } else if (nums[L] + nums[R] < target) {
                    L++;
                } else {
                    //L在第一位时不用比较和前一位是否相等的
                    if (L == 0 || nums[L - 1] != nums[L]) {
                        //List<Integer> res = new ArrayList<>();
                        //res.add(nums[L]);
                        //res.add(nums[R]);
                        //ans.add(res);
                        ans.add(new ArrayList<>(Arrays.asList(nums[L], nums[R])));
                    }
                    L++;
                }
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
